#include<iostream>
#include<vector>
using namespace std;
int k,n,m;
const int maxn=1000;
int color[maxn],cnt;
vector<int> nex[maxn];
bool check(int x)
{
    for(int i=0;i<nex[x].size();i++)
    {
        if(color[x]==color[nex[x][i]])
        return false;
    }
    return true;
}
void dfs(int now)
{
    if(now==n+1)
    {
        cnt++;
        return;
    }
    for(int i=1;i<=m;i++)
    {
        color[now]=i;
        if(check(now)) {
            dfs(now+1);
        }
        color[now]=0;
    }
}
int main()
{
    int x,y;
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++)
    {
        cin>>x>>y;
        nex[x].push_back(y);
        nex[y].push_back(x);
    }
    dfs(1);
    cout<<cnt;
    return 0;
}